/**
 * 面试题24：反转链表
 */
public class Offer_24 {
    /**
     * 方法二：迭代
     * <p>
     * 时间复杂度：O(n)
     * <p>
     * 空间复杂度：O(1)
     */
    public ListNode reverseList(ListNode head) {
        ListNode prev = null;
        ListNode cur = head;
        while (cur != null) {
            ListNode nextNode = cur.next;
            cur.next = prev;
            prev = cur;
            cur = nextNode;
        }
        return prev;
    }

    /**
     * 方法一：递归
     * <p>
     * 时间复杂度：O(n)
     * <p>
     * 空间复杂度：O(n)
     */
    public ListNode reverseList1(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode newHead = reverseList(head.next);
        head.next.next = head;
        head.next = null;
        return newHead;
    }

    public static void main(String[] args) {
        // 构造链表
        // 虚拟头节点
        ListNode dummyHead = new ListNode();
        ListNode cur = dummyHead;
        for (int i = 1; i < 10; i++) {
            cur.next = new ListNode();
            cur.next.val = i;
            cur = cur.next;
        }
        // 打印链表
        cur = dummyHead;
        printListNode(cur.next);

        // 反转链表
        Offer_24 solution = new Offer_24();
        ListNode ans = solution.reverseList(dummyHead.next);
        // 打印结果
        printListNode(ans);
    }

    public static void printListNode(ListNode node) {
        System.out.print("[");
        while (node != null) {
            System.out.print(node.val + " -> ");
            node = node.next;
        }
        System.out.println("null]");
    }
}
